public class NumMatrix {
    //https://leetcode.cn/problems/range-sum-query-2d-immutable/
    //二维区域和检索 - 矩阵不可变
    //二维前缀和, 这里我不使用多加一行一列的情况下, 要做边界条件处理
    public static int[][] matrix;
    public NumMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(i >= 1){
                    matrix[i][j] += matrix[i - 1][j];
                }
                if(j >= 1){
                    matrix[i][j] += matrix[i][j - 1];
                }
                if(i >= 1 && j >= 1){
                    matrix[i][j] -= matrix[i - 1][j - 1];
                }
            }
        }
        this.matrix = matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        //先(0,0) - (x,y)的位置
        int sum = 0;
        sum += matrix[row2][col2];
        if(row1 >= 1){
            sum -= matrix[row1 - 1][col2];
        }
        if(col1 >= 1){
            sum -= matrix[row2][col1 - 1];
        }
        if(row1 >= 1 && col1 >= 1){
            sum += matrix[row1 - 1][col1 - 1];
        }
        return sum;
    }
}
